//实现红黑树，首先要确定红黑树的节点，其次再实现树结构
#include <iostream>
#include <cassert>
#include <stack>
using namespace std;
//红黑树的节点应该包含
//1. 存放的值；2.指向左右子树的指针 3.存放节点颜色 4. 指向父亲的指针
//红黑树节点的实现，必须为public，我们需要在红黑树类中使用RBTreeNode的成员变量
//////////////////////////////////////////////////
////////////////////RBTreeNode////////////////////
enum Color
{
    red,
    black
};
template <class V>
struct RBTreeNode
{
    RBTreeNode(const V& data)
        : _data(data)
        , _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _color(red)     ///插入的新节点默认是红色节点，保证每条路径的黑色节点数目相同
    {}

    V _data;
    RBTreeNode<V>* _left;
    RBTreeNode<V>* _right;
    RBTreeNode<V>* _parent;
    Color _color;
};
///////////////////////////////////////////////////
template <class V>
class RBTree_Iterator
{
public:
    typedef RBTreeNode<V> Node;
    typedef RBTree_Iterator<V> Self;

    RBTree_Iterator(Node* node)
        : _node(node)
    {}
    
    //内置类型
    V& operator*()
    {
        return _node->_data;   
    }
    
    //自定义类型
    V* operator->()
    {
        return &_node->_data;
    }
    
    bool operator==(const Self& it)
    {
        return _node == it._node;
    }

    bool operator!=(const Self& it)
    {
        return _node != it._node;
    }

    //前置++
    Self& operator++()
    {
        if(_node == nullptr)
        {
            cout << "错误" << endl;
            assert(false);
            return *this;
        }
        //右子树不为空，下一个元素为右子树的最左节点
        if(_node->_right)
        {
            _node = _node->_right;
            while(_node->_left)
            {
                _node = _node->_left;
            }
            return *this;
        }
        //右子树为空
        else
        {
            while(_node->_parent) //到根结点结束
            {
                //当前节点为父亲的左节点，则父亲就是下一个元素
                if(_node == _node->_parent->_left)
                {
                    _node = _node->_parent;
                    return *this;
                }
                    //为右节点，则表明以父节点为根的子树已经访问完了，往上查找
                else
                {
                    _node = _node->_parent;
                }
            }
            _node = nullptr;
        }
        return *this;
    }

    //后置++
    Self operator++(int)
    {
        Self copy = *this;
        ++(*this);
        return copy;
    }
    Self& operator--()
    {
        //end()
        if(_node == nullptr)
        {

        }
        //左子树不为空，则上一个元素为左子树的最右节点
        if(_node->_left)
        {
            _node = _node->_left;
            while(_node->_right)
            {
                _node = _node->_right;
            }
            return *this;
        }
        //左子树为空，当前子树已经访问过
        else
        {
            while(_node->_parent)
            {
                if(_node == _node->_parent->_right)
                {
                    _node = _node->_parent;
                    return *this;
                }
                else
                {
                    _node = _node->_parent;
                }
            }
            _node = nullptr;
            return *this;
        }

    }

    Self operator--(int)
    {
        Self copy = *this;
        --(*this);
        return copy;
    }
private:
    Node* _node;
};
///////////////////////////////////////////////////
//实现完RBTreeNode后，开始实现RBTree，而RBTree只希望被访问成员函数
//所以成员函数public，成员变量private
template <class K, class V, class KeyOfVal>
class RBTree
{
public:
    typedef RBTreeNode<V> Node;
    typedef RBTree_Iterator<V> iterator;

    //iterator begin
    iterator begin()
    {
        Node* cur = _root;
        while(cur && cur->_left)
        {
            cur = cur->_left;
        }
        return iterator(cur);
    }

    //iterator end
    iterator end()
    {
        return iterator(nullptr);
    }

    //插入节点
    bool insert(const V& data)
    {
        //空树
        if(_root == nullptr)
        {
            _root = new Node(data);
            //创建失败
            if(_root == nullptr)
            {
                perror("new error");
                return false;
            }
            //创建成功，根结点必须为黑色节点
            _root->_color = black;
            return true;
        }
        //不为空树
        else
        {
            Node* cur = _root;
            Node* parent = cur;
            KeyOfVal kov;
            while(cur)
            {
                if(kov(cur->_data) > kov(data))
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if(kov(cur->_data) < kov(data))
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else
                {
                    perror("insert a same data, insert error");
                    return false;
                }
            }

            cur = new Node(data);
            if(kov(parent->_data) > kov(data))
            {
                parent->_left = cur;
            }
            else
            {
                parent->_right = cur;
            }
            cur->_parent = parent;
            //////////////////////////
            //判断颜色问题
            AssertColor(parent, cur);
            return true;
        }
        
    }
private:
    Node* _root = nullptr;
    //递归版本
    bool CheckNumB_R(Node* root, int num, int count)
    {
        if(root == nullptr)
        {
            if(num != count)
                return false;
            return true;
        }

        if(root->_color == black)
            ++count;

        return CheckNumB_R(root->_left, num, count) && CheckNumB_R(root->_right, num, count);
    }
    //非递归版本
    bool CheckNumB(Node* root)
    {
        vector<Node*> check; //检查是否右子树已经遍历过了，要记录所有走过的右侧的节点
        stack<Node*> s;      //存路径
        Node* cur = root;
        Node* pre = nullptr;
        int num = 0;         //记录黑色节点的个数
        int copy = -1;       //记录前一条路径的黑色节点的个数

        while(cur || !s.empty())
        {
            int flag = 0;

            while(cur)  //遍历每条路径
            {
                if(cur->_color == black)
                {
                    ++num;
                }
                s.push(cur);
                cur = cur->_left;
                flag = 1;
            }

            if(flag == 1) //说明走的路径是新的
            {
                if(copy != -1)
                {
                    if(copy != num) //前一个路径的黑色节点个数不等于当前路径的黑色节点个数，不满足条件，返回false
                        return false;
                }
                copy = num;
            }

            if(s.top()->_right == nullptr || CheckRepeated(check, s.top()->_right))  //右子树为空 / 右子树走过了，路径结束，换路径
            {
                if(s.top()->_color == black)
                {
                    --num;
                }
                s.pop();
            }
            else //右子树不为空，且没有走过，就去遍历右子树
            {
                cur = s.top()->_right;
                pre = cur;
                check.push_back(pre);
            }
        }
        //遍历完每条路径后，黑色节点个数都相等
        return true;

    }
    //检查右子树是否已经遍历过了
    bool CheckRepeated(vector<Node*>& check, Node*& pre)
    {
        for(auto e : check)
        {
            if(pre == e)
            {
                return true;
            }
        }
        return false;
    }


    //检查根是否为黑色
    bool CheckRoot()
    {
        if(_root == nullptr)
            return true;

        return _root->_color == black;
    }

    //检查是否有连续的红色节点
    bool CheckColor(Node* root)
    {
        if(root == nullptr)
            return true;
        return CheckColor(root->_left)
               && CheckColor(root->_right)
               && (root->_color == black || root->_parent->_color == black);
    }

    void AssertColor(Node*& parent, Node*& cur)
    {

        while(parent && parent != _root)
        {
            Node* grandfather = parent->_parent;
            Node* uncle = (parent == grandfather->_left) ? grandfather->_right : grandfather->_left;
            //插入位置的父亲为红色节点，需要处理
            if(cur->_color == red && parent->_color == red)
            {
                //叔叔存在，且为红
                if(uncle && uncle->_color == red)
                {
                    parent->_color = uncle->_color = black;
                    grandfather->_color = red;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                    //叔叔存在,且为黑 / 叔叔不存在  旋转+变色
                else
                {
                    if(uncle == grandfather->_left)
                    {
                        if(cur == parent->_right)
                        {
                            RotationL(grandfather);
                            parent->_color = black;
                            grandfather->_color = red;
                        }
                        else
                        {
                            RotationR(parent);
                            RotationL(grandfather);
                            cur->_color = black;
                            grandfather->_color = red;
                        }
                    }
                    else
                    {
                        if(cur == parent->_left)
                        {
                            RotationR(grandfather);
                            parent->_color = black;
                            grandfather->_color = red;
                        }
                        else
                        {
                            RotationL(parent);
                            RotationR(grandfather);
                            cur->_color = black;
                            grandfather->_color = red;
                        }
                    }
                    break;
                }
            }
                //插入位置的父亲为黑色节点，不需要处理
            else
            {
                break;
            }
        }

        _root->_color = black;
    }
    void RotationL(Node* parent)
    {
        Node* pR = parent->_right;
        Node* pRL = pR->_left;

        parent->_right = pRL;
        if(pRL)
            pRL->_parent = parent;
        pR->_left = parent;
        Node* ppnode = parent->_parent;
        parent->_parent = pR;

        if(parent == _root)
        {
            _root = pR;
            pR->_parent = nullptr;
        }
        else
        {
            if(ppnode->_left == parent)
                ppnode->_left = pR;
            else
                ppnode->_right = pR;
            pR->_parent = ppnode;
        }

    }
    void RotationR(Node* parent)
    {
        Node* pL = parent->_left;
        Node* pLR = pL->_right;

        parent->_left = pLR;
        if(pLR)
            pLR->_parent = parent;
        pL->_right = parent;
        Node* ppnode = parent->_parent;
        parent->_parent = pL;

        if(_root == parent)
        {
            _root = pL;
            pL->_parent = nullptr;
        }
        else
        {
            if(ppnode->_left == parent)
                ppnode->_left = pL;
            else
                ppnode->_right = pL;
            pL->_parent = ppnode;
        }

    }
};

















